FIG. 1 illustrates an exemplary Host Bus Adapter (HBA) 100 within a host computer for enabling the host computer to communicate with storage devices in a storage area network (SAN) over a link such as a Fibre Channel (FC) link 102. Frames of Receive (Rx) data 104 received over the link 102 are received by a port 106 within the HBA 100, and frames of Transmit (Tx) data 112 originating from the HBA 100 are transmitted over the link 102 by the port 106. Before the Rx data 104 can be forwarded to host memory (not shown), it must be first placed in an area of local memory 108 reserved for storing the Rx data 104. This area of local memory 108 starts from a base address 110. Local memory area 108 may be partitioned into contiguous equal-size slots or buffers 114, where each slot or buffer 114 holds one frame of Rx data 104. Although the buffers 114 may be contiguous within local memory area 108, the buffers 114 may be written to or read from in a non-contiguous manner, resulting in a patchwork of empty or free buffers spread out over the local memory area 108. New Rx data 104 may therefore be stored into free buffers in non-contiguous buffer locations spread out over the local memory area 108.
Before a frame of Rx data 104 can be stored into the local memory area 108, the address of a free buffer in the local memory area 108 must be provided. However, because Rx data 104 may be received at rates of 4 Gbits/second or higher, the address must be generated quickly. One of the biggest challenges facing serial protocol designs such as FC is managing the buffers 114 at high link speeds. For the case of Rx data 104, the HBA must make a decision on where to store the incoming frame within a short amount of time or run the risk of overrunning a receive First In First Out memory (FIFO) in the port 106 or having to stall the reception of subsequent frames. Even state-of-the-art microprocessor speeds cannot keep up with increasing link speeds and enable the microprocessor to detect that a frame is being received, calculate the memory address to store the frame data, load the memory address into hardware, and have hardware use the memory address to store the incoming frame.
To assist the HBA 100 in generating the addresses of free buffers, the buffers 114 are assigned buffer numbers 116 (e.g. 0 to N−1), where N is the number of buffers in the local memory area 108. For ease of implementation, the number of buffers N in the local memory area 108 is typically chosen so that it can be represented by M bits (e.g. 256 buffers, which can be represented by eight bits), and the size of each buffer is typically chosen to be a power of two number of bytes (e.g. 211=2048 bytes). In such an implementation, the starting address for each buffer is a multiple of the power of two (e.g. 1024 bytes, 2048 bytes, 4096 bytes, etc., not including the base address 110).
Within frame Rx queue 118, the buffer numbers 116 of free buffers are stored in a queue such as a Free Buffer FIFO (FB FIFO) queue 120. When the port 106 receives a frame of Rx data 104, Rx frame control information 122 is sent to a frame buffer address generator 124 along with the buffer number 126 of the next available free buffer stored in FB FIFO queue 120. The frame buffer address generator 124 then generates the complete or full frame buffer address 128 of the next available frame buffer for storing the frame of Rx data 104. If the frame size of the Rx data 104 is a power of two number of bytes (e.g. 211=2048 bytes), then the generation of the complete address 128 by frame buffer address generator 124 is trivial. FIG. 2 illustrates the full P-bit frame buffer address 228 for a local memory area, where the full frame buffer address 228 is simply the concatenation of a base address 210 and a buffer number 226.
Similarly, before the Tx data 112 from the host memory can be transmitted over the link 102, it must be first placed in an area of local memory 142 reserved for storing the Tx data 112. This area of local memory 142 starts from a base address 144. Local memory area 142 may be partitioned into contiguous equal-size slots or buffers 146, where each slot or buffer 146 holds one frame of Tx data 112. Although the buffers 146 may be contiguous within local memory area 142, the buffers 146 may be written to or read from in a non-contiguous manner, resulting in a patchwork of empty or free buffers spread out over the local memory area 142. New Tx data 112 may therefore be stored into free buffers in non-contiguous buffer locations spread out over the local memory area 142.
Before a frame of Tx data 112 can be stored into the local memory area 142, the address of a free buffer in the local memory area 142 must be provided. To assist the HBA 100 in generating the addresses of free buffers, the buffers 146 are assigned buffer numbers 148 (e.g. 0 to N−1), where N is the number of buffers in the local memory area 142. Note that the storing of Tx data 112 into local memory is under program control. To retrieve the Tx data 112, hardware in the HBA 100 takes a buffer number and a base address to produce a frame start address. The buffer number is included in the information written into a hardware queue to make the Tx data available for transmission. The hardware then retrieves the data from local memory and transmits it on the link. For ease of implementation, the number of buffers N in the local memory area 142 is typically chosen so that it can be represented by M bits (e.g. 256 buffers, which can be represented by eight bits), and the size of each buffer is typically chosen to be a power of two number of bytes (e.g. 211=2048 bytes). In such an implementation, the starting address for each buffer is a multiple of the power of two (e.g. 1024 bytes, 2048 bytes, 4096 bytes, etc., not including the base address 110).
Within frame Tx queue 130, the buffer numbers 138 of free buffers are stored in a FB FIFO queue 132. When the host generates a frame of Tx data 112, Tx frame control information 134 is sent to a frame buffer address generator 136 along with the buffer number 138 of the next available free buffer stored in FB FIFO queue 132. The frame buffer address generator 136 then generates the full frame buffer address 140 of the next available frame buffer for storing the frame of Tx data 112 in a manner similar to that described above with respect to Rx data 104 and FIG. 2.
However, a difficulty arises when the frame size of the Rx data 104 and TX data 112 is not a power-of-two number of bytes. For example, the frame size (payload only) of a FC frame is 2112 bytes.
One conventional solution pre-calculates and loads the full frame buffer starting address into the FB FIFO so that it can be retrieved by Rx or free frame buffer address generation logic when necessary. The drawback to this approach is that the hardware must store and manage several bytes for each frame buffer starting address, which may comprise a large number of bits (e.g. 23 bits). Depending on the number of frames that need to be buffered, this approach could require a large Random Access Memory (RAM) to store all the free frame buffer starting addresses.
Another conventional approach is to use dedicated frame buffers (small RAMs) to store the frame payload data. The problem with this approach is that using many small RAMs is not efficient in an Application Specific Integrated Circuit (ASIC) if a large number of frame buffers are required. In terms of ASIC RAM, it is far more efficient to use larger RAMs that can contain multiple frame buffers. Also, the dedicated frame buffer approach implies a fixed number of frame buffers that cannot be changed.
Still another conventional solution to this problem is to utilize a frame buffer size equal to smallest the power of two that is greater than the frame size. In the FC example, because the frame size is 2112 bytes, the smallest power of two that is greater than the frame size is 212=4096 bytes. The full address generation would be trivial, as described above, and each 2112 byte frame would be stored into a 4096 byte frame buffer. However, this conventional solution wastes memory, because there are unused bytes in each frame buffer. Firmware-controlled structures may be stored in the unused portions of the buffers to reduce the wasted memory space, but it is inefficient for the firmware to be fragmented into slivers of memory.
Therefore, in situations where the frame size is not a power of two number of bytes, there is a need to store frames of data in frame buffers that have been sized to reduce wasted memory, store only the buffer numbers of free buffers (rather than a full address) in a FB FIFO, and use the buffer numbers to efficiently identify the full frame buffer address of free frame buffers that are to be used to store the frame data.